package uestc.lj.basicPromotion.tree;

import java.util.List;

/**
 * @Author:Crazlee
 * @Date:2021/11/27
 */
public class Code02_MaxHappy {
	public static class Employee {
		public int happy;
		public List<Employee> nexts;
	}

	public static class Info {
		public int invitedMaxHappy;
		public int unInvitedMaxHappy;

		public Info(int invitedMaxHappy, int unInvitedMaxHappy) {
			this.invitedMaxHappy = invitedMaxHappy;
			this.unInvitedMaxHappy = unInvitedMaxHappy;
		}
	}

	public static int getMaxHappy(Employee boss) {
		Info info = process(boss);
		return Math.max(info.invitedMaxHappy, info.unInvitedMaxHappy);
	}

	public static Info process(Employee employee) {
		//基层员工
		if (employee.nexts.isEmpty()) {
			return new Info(employee.happy, 0);
		}
		//当前员工参与的快乐初始值
		int invitedMaxHappy = employee.happy;
		//当前员工不参与的快乐初始值
		int unInvitedMaxHappy = 0;
		//对当前员工的下属员工遍历
		for (Employee next : employee.nexts) {
			Info nextInfo = process(next);
			//当前员工参与的话，那其下属员工必须不参与
			invitedMaxHappy += nextInfo.unInvitedMaxHappy;
			//当前员工不参与的话，求下属员工参与和不参与的最大值
			unInvitedMaxHappy += Math.max(nextInfo.invitedMaxHappy, nextInfo.unInvitedMaxHappy);
		}
		return new Info(invitedMaxHappy, unInvitedMaxHappy);
	}
}
